InterviewQuestions

Two Pointers & Linked List

The Two Pointer technique is one of the most elegant tools in algorithm design. It reduces time complexity by avoiding redundant traversal and is widely used in string, array, and linked list problems.
This chapter explains when and how to use it, the logic behind fixed and floating pointers, and how this pattern connects to linked list problems.

When to Use Two Pointers

Two Pointers are typically used in:

  1. String Manipulation — e.g., reversing or checking palindromes in place.
  2. Linear Structure Problems — such as LinkedList, Array, Substring, and Sliding Window.
  3. Search or Sort Problems — such as finding pairs, merging intervals, or sorting colors.

Understanding Fixed and Float Pointers

To master this pattern, ask yourself two key questions before solving:

1️⃣ Who is the Fixed Pointer?
2️⃣ Who is the Float Pointer?

✅ Fixed Pointer

The Fixed Pointer marks a boundary or stable reference point.
It doesn’t move (or moves slowly) while the other pointer explores ahead.
Example: In Remove Duplicates from Sorted Array, the fixed pointer stays at the “last unique” element.

🔁 Float Pointer

The Float Pointer scans or explores forward to find a valid candidate or trigger a condition.
Once a valid condition is found, it helps update the fixed pointer.
In most problems, the float pointer moves linearly (usually right++ or fast = fast.next).

🧮 Classic Problems by Category

1️⃣ Array & String Problems

Problem Idea Key Operation
1. Two Sum Use hash table or two pointers after sorting. Move inward depending on sum < target or sum > target.
15. 3Sum Fix one pointer, use two others for pair search. nums[i] + nums[l] + nums[r] == 0 → shrink window.
611. Valid Triangle Number Sort array, then use two pointers inside loop. Count valid pairs when nums[l] + nums[r] > nums[i].
283. Move Zeroes Fixed = non-zero position, Float = traversal pointer. Swap elements in place.
26. Remove Duplicates from Sorted Array Fixed = slow pointer for unique elements. Float = fast pointer scanning array.
75. Sort Colors (Dutch Flag) Use three pointers: low, mid, high. Partition by swapping 0s, 1s, 2s.
56. Merge Intervals Sort intervals and merge overlapping ones. Track end points using slow/fast pointers.

2️⃣ Linked List Problems

Problem Idea Key Pattern
876. Middle of the Linked List Fast pointer moves 2 steps, slow 1 step. Return slow when fast reaches end.
206. Reverse Linked List Use three pointers: prev, curr, next. Reverse direction iteratively.
234. Palindrome Linked List Find middle, reverse second half, compare both. Restore list if needed.
141. Linked List Cycle Floyd’s Cycle Detection. If fast == slow, cycle exists.
142. Linked List Cycle II When fast meets slow, reset one to head. Move both one step to find entry point.

3️⃣ Sorting & Merge Problems

Problem Idea Approach
912. Sort an Array Use Merge Sort or Quick Sort. Merge step uses two pointers to combine arrays.

Common Two-Pointer Movement Patterns

Same Direction (Fast & Slow)

Used in:

  • Cycle detection
  • Remove duplicates
  • Move zeroes
  • Sliding window problems

Example:

1
2
3
4
5
slow = 0
for fast in range(len(nums)):
    if nums[fast] != 0:
        nums[slow], nums[fast] = nums[fast], nums[slow]
        slow += 1

Opposite Direction (Left & Right)

Used in:

  • Two Sum
  • 3Sum
  • Valid Triangle Number

Example:

1
2
3
4
5
6
7
8
9
l, r = 0, len(nums) - 1
while l < r:
    total = nums[l] + nums[r]
    if total == target:
        return True
    elif total < target:
        l += 1
    else:
        r -= 1

Summary

Concept Explanation
Fixed Pointer Holds boundary or condition anchor
Float Pointer Moves forward to test or extend the condition
Core Advantage Reduce redundant traversal from O(n²) → O(n)
Typical Usage Arrays, strings, and linked lists
Main Variants Fast–slow pointers, opposite pointers, triple pointers

The Two Pointer pattern is not about memorizing templates — it’s about understanding how two moving indices interact to reduce complexity.
Once you master the intuition behind fixed vs. float pointers, you’ll start seeing this pattern everywhere — from simple “move zeroes” problems to advanced “merge k intervals” or “detect cycles” questions.